import java.util.HashSet;

/**
 * 给定一个整数 n，返回 n 皇后不同的解决方案的数量。
 * <p>
 * 示例:
 * <p>
 * 输入: 4
 * 输出: 2
 * 解释: 4 皇后问题存在如下两个不同的解法。
 */
class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.totalNQueens(4));
    }

    private static int sum;

    /**
     * 很典型需要用回溯来处理变量可能性，使用集合存记录以去重
     *
     * @param n
     * @return
     */
    public int totalNQueens(int n) {
        sum = 0;
        // 纵向记录
        HashSet<Integer> set1 = new HashSet<>();
        // 右斜记录，相减一样
        HashSet<Integer> set2 = new HashSet<>();
        // 左斜记录，相加一样
        HashSet<Integer> set3 = new HashSet<>();
        for (int i = 0; i < n; i++) {
            // 放置
            set1.add(i);
            set2.add(i);
            set3.add(i);
            loop(0, n, set1, set2, set3);
            // 回溯
            set1.remove(i);
            set2.remove(i);
            set3.remove(i);
        }
        return sum;
    }

    /**
     * x,y的位置已经被放置，开始递归，只考虑下一层
     *
     * @param y
     * @param n
     * @param set1
     * @param set2
     * @param set3
     * @return
     */
    public void loop(int y, int n, HashSet<Integer> set1, HashSet<Integer> set2, HashSet<Integer> set3) {
        if (y == n - 1) {
            // 如果已经处理完毕，则处理为最后的结果
            sum++;
        }
        for (int i = 0; i < n; i++) {
            if (ok(i, y + 1, set1, set2, set3)) {
                // 放置
                set1.add(i);
                set2.add(i - y - 1);
                set3.add(i + y + 1);
                loop(y + 1, n, set1, set2, set3);
                // 回溯
                set1.remove(i);
                set2.remove(i - y - 1);
                set3.remove(i + y + 1);
            }
        }
    }

    /**
     * 判断此次防止是否合法
     *
     * @param x
     * @param y
     * @param set1
     * @param set2
     * @param set3
     * @return
     */
    public boolean ok(int x, int y, HashSet<Integer> set1, HashSet<Integer> set2, HashSet<Integer> set3) {
        if (set1.contains(x) || set2.contains(x - y) || set3.contains(x + y)) {
            return false;
        }
        return true;
    }
}